# https://leetcode.cn/problems/delete-and-earn/description/

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        cnt = [0] * 10010
        n = len(nums)
        mx = 0
        for xx in nums :
            cnt[xx] += 1
            mx = max(mx, xx)
        f = [[0] * 2 for _ in range(mx + 1)]
        # f[i][0/1] 0：不选 1：选
        # 转移 
        # 1. 选 的上一个一定是不选 f[i][1] = f[i - 1][0] + x * cnt[x]
        # 2. 不选 从上一个选与不选中找最大的 f[i][0] = max(f[i - 1][0], f[i - 1][1])
        for i in range(1, mx + 1):
            f[i][1] = f[i - 1][0] + i * cnt[i]
            f[i][0] = max(f[i - 1][1], f[i - 1][0])
        return max(f[mx][0], f[mx][1])
